1. Field of the Invention
This invention relates generally to a method and apparatus for performing error correction on digital data using a Reed-Solomon code and, more particularly, to a method and apparatus for decoding a Reed-Solomon code wherein error symbols are corrected during decoding by error vectors obtained by a series of product sum arithmetic operations.
2. Description of the Background
One error correction code that is typically used in compact audio discs is the so-called CIRC correction code. CIRC is an acronym for Cross Interleave Reed-Solomon Code. In the case of the CIRC correction code, the encoding process of the (28, 24) Reed-Solomon code (C2 code) is performed for twenty-four data symbols, with each symbol consisting of 8 bits. In such typical audio applications each audio sample is 16 bits, which is formed of two symbols of 8 bits each. Thus, each 8-bit symbol is either the upper or lower side of an audio sample of one of the two channels of stereophonic audio data. These data symbols are in a first state of arrangement and, next, the data is rearranged from the first arrangement state to a second state of arrangement by an interleave operation. The encoding process of the (32, 28) Reed-Solomon code (C1 code) is then executed for the twenty-eight symbols that are now in the second arrangement state. When decoding the CIRC correction code, the C1 decoding is performed first, then the deinterleave is performed and, thereafter, the C2 decoding is performed.
There are already known various methods of decoding the CIRC correction code, and examples of such methods are disclosed in several U.S. patents, for example, U.S. Pat. Nos. 4,546,474; 4,476,562; and 4,497,058. On the other hand, there are also known various methods of decoding the Reed-Solomon code, and examples of such methods are disclosed in U.S. Pat. No. 4,476,562 and in U.S. patent application Ser. No. 767,783, assigned to the Assignee hereof.
According to the conventional decoding methods of the CIRC correction code, error processing up to and including double-error correction is executed in the C1 decoding in the first stage, and double-error correction is executed in the C2 decoding at the next stage by referring to pointer information that is derived from the C1 decoding.
One method of decoding the error correction code that has been proposed is the so-called erasure correction method, in which the location of the error symbol is indicated by pointer information and the necessary correction is performed on this error symbol. In the case of the above-mentioned C1 and C2 codes, detection and correction up to and including double errors (two symbols) can be respectively performed, however, if the error location is already known, then error correction up to and including quadruplex errors (four symbols) can be performed. Therefore, in order to raise the error correction capability, it has been preferred to perform the erasure correction method of decoding the error. Furthermore, the erasure correction method has been found to be particularly effective in correcting burst errors. On the other hand, in order to perform the erasure correction operation properly, the error locations must be preliminarily known from the pointer information and, moreover, the reliability of that pointer information must be relatively high.
According to the conventional coding method of the CIRC correction code, error correction up to and including double errors is executed in the C1 decoder. In such case, because there is a fear of the occurrence of triple errors, which of course could not be corrected, the C1 pointer is sent to the C2 decoder in the next stage, so that error correction is executed in the C2 decoder using the C1 pointer.
More specifically, in the case of the conventional CIRC correction code, as shown for example in FIG. 6, the series of the C1 code (C1 series) is formed by 32 symbols that are alternately included in two adjacent frames (one frame: 32 symbols). The series of the C2 code (C2 series) is formed by 28 symbols that are included in predetermined ones of 108 consecutive frames. Because the interleave length of the C1 series is shorter than that of the C2 series, when a fast-forward reproduction operation, such as queuing or review, is performed, a problem occurs in that some frames are dropped and the continuity of the frames is lost. That is, the C1 pointer is used to indicate the presence of errors in the one frame before and after the point of the discontinuity, however, the C1 pointer only indicates the absence of the errors in the other frame. On the other hand, the interleave length of the C2 series has 108 frames, and these 108 frames will include the point of discontinuity. Thus, this is also not the correct C2 series. Upon performing the erasure correction for the incorrect C2 series by use of the foregoing C1 pointer, the error correction will be incorrect.
To solve this problem of incomplete or incorrect error correction when performing error correction of the CIRC correction code, wherein the maximum error correcting capability is obtained by the erasure correction method, there has been proposed an error correction method whereby the C1 decoding and C2 decoding are executed twice in a specific order. That order might be, for example, C1 decoding, followed by C2 decoding, followed by C1 decoding, and followed by C2 decoding. In the first C2 decoding, erasure correction is performed using the C1 pointer obtained by the C1 decoding at the front stage and the erroneous correction that may occur at this erasure correction is prevented by the second C1 decoding and the C2 decoding, which are similar to the conventional method of decoding the CIRC correction code.
In using such an improved error correction method, it is necessary to perform the erasure correction in a short time period. In the case of the Reed Solomon code, generally, the erasure correction is performed by solving the following equation. ##EQU1## where, .nu.=0 to d-2,
n: the number of erasure symbols, PA1 X.sub.j : jth error location, PA1 S.nu.: syndrome, PA1 Y.sub.j : jth error vector, PA1 d: Hamming distance of the code.
For example, when four symbols are included, the syndromes are as follows: ##EQU2##
The code length of the C2 code is 28. In the case where the error vector Y.sub.1 exists in W.sub.n with respect to the received symbols W.sub.0 to W.sub.27, then it is seen that ##EQU3## When it is assumed that the one error is included in the symbol W.sub.n, and it is further assumed that (X.sub.1 =.alpha..sup.n), then the syndromes can be written as: ##EQU4## where "j" in X.sub.j and Y.sub.j denotes the order assigned to the errors in the received data.
Similarly, if it is assumed that the errors exist in, for example, four symbols, such as W.sub.0, W.sub.5, W.sub.10, and W.sub.18, among the 28 symbols W.sub.0 to W.sub.27 that are received, that is: ##EQU5## and further assuming that:
X.sub.1 =.alpha..sup.0, X.sub.2 =.alpha..sup.5, X.sub.3 =.alpha..sup.10, X.sub.4 =.alpha..sup.18 then when the errors exist in the four symbols, the following syndromes are derived. ##EQU6##
When the error locations X.sub.1 to X.sub.4 are known from the pointer information, then the error vectors Y.sub.1 to Y.sub.4 are obtained as follows: ##EQU7##
According to the foregoing erasure correction method, there are a total of eighty-four calculation operations necessary to obtain the error vectors Y.sub.1 to Y.sub.4, more specifically, the eighty-four calculations are comprised of addition: 40 times, multiplication: 40 times, and division: 4 times.
When the foregoing processes are repetitively performed for all of the code series, there are problems that the number of arithmetic operations increases greatly, and the decoding time is correspondingly prolonged. One method of solving such problems has been disclosed in U.S. patent application Ser. No. 767,783. According to the erasure correction method disclosed therein the number of necessary arithmetic operation in the erasure correction for the product code can be effectively reduced, but such method is not so effective for cross interleave codes, such as the foregoing CIRC correction code.